//
// Created by wangwanlong on 2024/6/17.
//

#ifndef MCGPP_SPARSE_SET_H
#define MCGPP_SPARSE_SET_H
#include "typedef.h"
#include <limits>
#include <memory>
#include <utility>
namespace mcgpp {
  namespace ds {
    template <typename ValueType = int32_t,
            typename Derived = int32_t>
    class SparseSetBase {
    public:
      SparseSetBase(const SparseSetBase&) = delete;
      SparseSetBase& operator= (const SparseSetBase&) = delete;

      SparseSetBase& operator= (SparseSetBase&& other) {
        _sparse = std::move(other._sparse);
        _size = other._size;
        _dense = other._dense;

        other._size = 0;
        other._dense = nullptr;
        return *this;
      }

      ValueType size() const {
        return _size;
      }

      bool contains(const ValueType value) const {
        return static_cast<const Derived*>(this)->containsImpl(value);
      }

      void add(const ValueType value) {
        static_cast<Derived*>(this)->addImpl(value);
      }

      const ValueType* begin() const {
        return _dense;
      }

      const ValueType* end() const {
        return _dense + _size;
      }

      void clear() {
        static_cast<Derived*>(this)->clearImpl();
      }

    protected:
      explicit SparseSetBase(const ValueType k) :
              _size(0),
              _sparse(std::make_unique<ValueType[]>(2 * static_cast<size_t>(k))),
              _dense(nullptr) {
        for (ValueType i = 0; i < 2 * k; ++i) {
          _sparse[i] = std::numeric_limits<ValueType>::max();
        }
        _dense = _sparse.get() + k;
      }

      ~SparseSetBase() = default;

      SparseSetBase(SparseSetBase&& other) :
              _size(other._size),
              _sparse(std::move(other._sparse)),
              _dense(other._dense) {
        other._size = 0;
        other._sparse = nullptr;
        other._dense = nullptr;
      }

      ValueType _size;
      std::unique_ptr<ValueType[]> _sparse;
      ValueType* _dense;
    };

    template <typename ValueType = int32_t>
    class SparseSet final : public SparseSetBase<ValueType, SparseSet<ValueType> >{
      using Base = SparseSetBase<ValueType, SparseSet<ValueType> >;
      friend Base;

    public:
      explicit SparseSet(const ValueType k) :
              Base(k) { }

      SparseSet(const SparseSet&) = delete;

      SparseSet(SparseSet&& other) :
              Base(std::move(other)) { }


      SparseSet& operator= (SparseSet&& other) {
        if (this != &other) {
          Base::operator= (std::move(other));
        }
        return *this;
      }

      SparseSet& operator= (SparseSet&) = delete;

      ~SparseSet() = default;

      void remove(const ValueType value) {
        const ValueType index = _sparse[value];
        if (index < _size && _dense[index] == value) {
          const ValueType e = _dense[--_size];
          _dense[index] = e;
          _sparse[e] = index;
        }
      }

    private:
      bool containsImpl(const ValueType value) const {
        const ValueType index = _sparse[value];
        return index < _size && _dense[index] == value;
      }

      void addImpl(const ValueType value) {
        const ValueType index = _sparse[value];
        if (index >= _size || _dense[index] != value) {
          _sparse[value] = _size;
          _dense[_size++] = value;
        }
      }

      void clearImpl() {
        _size = 0;
      }

      using Base::_sparse;
      using Base::_dense;
      using Base::_size;
    };

  }  // namespace ds
}  // namespace kahypar
#endif //MCGPP_SPARSE_SET_H
